package pers.guesswho;

import java.io.*;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Random;

import pers.guesswho.Guess.GuessType;
import pers.guesswho.RandomGuessPlayer.Attribute;
import pers.guesswho.RandomGuessPlayer.Person;

/**
 * Binary-search based guessing player.
 * This player is for task C.
 *
 * You may implement/extend other interfaces or classes, but ensure ultimately
 * that this class implements the Player interface (directly or indirectly).
 */
public class BinaryGuessPlayer implements Player
{
	// 候选人组
	protected List<Person> persons = new ArrayList<>();
	// 候选属性集
	protected List<Attribute> attributes = new ArrayList<>();
	// 选择人
	protected Person chosenPerson;
	// 选择人名称
	protected String chosenName;
	// 决策树
	protected TreeNode rootNode = new TreeNode("", "", "");
	// 决策树索引
	protected TreeNode currentNode = new TreeNode("", "", "");

    /**
     * Loads the game configuration from gameFilename, and also store the chosen
     * person.
     *
     * @param gameFilename Filename of game configuration.
     * @param chosenName Name of the chosen person for this player.
     * @throws IOException If there are IO issues with loading of gameFilename.
     *    Note you can handle IOException within the constructor and remove
     *    the "throws IOException" method specification, but make sure your
     *    implementation exits gracefully if an IOException is thrown.
     */
    public BinaryGuessPlayer(String gameFilename, String chosenName)
        throws IOException
    {
    	// 构造方法初始化数据
		this.chosenName = chosenName;
		BufferedReader gameReader = new BufferedReader(new FileReader(gameFilename));
		String line;
		Person person = new Person();
		int attrLength = 0;// 标记特征个数
		int attrFlag = 0;// 标记当前用户拥有的特征个数
		while ((line = gameReader.readLine()) != null) {

			if (line.length() == 0) {
				// 读到回车说明下一行是候选人名
				// 下一个候选人后将前一个候选人的信息保存进players
				line = gameReader.readLine();
				person = new Person();
				person.setName(line);
			} else if (line.length() != 0 && person.getName() != null) {
				// 将候选人的特性信息保存在实体类Person的Attributes中
				String[] fields = line.split(" ");
				HashMap<String, String> attr = new HashMap<>();
				person.getAttributes().put(fields[0], fields[1]);
				attrFlag++;
			} else {
				// 存储特征值
				String[] fields = line.split(" ");
				Attribute attribute = new Attribute();
				attribute.setAttrName(fields[0]);
				for (int i = 1; i < fields.length; i++) {
					attribute.getAttrVal().add(fields[i]);
				}
				attributes.add(attribute);
				attrLength++;
			}
			// 判断所有属性是否存储结束,若保存当前person对象
			if (attrFlag == attrLength) {
				if (chosenName.equals(person.getName())) {
					chosenPerson = person;
				}
				persons.add(person);
				attrFlag = 0;
			}

		}
		if (chosenPerson==null) {
			System.err.println("Uknown chosenName: " + chosenName);
		}
		
		//构造决策树
		List<Integer> personNum=new ArrayList<Integer>();
        for(int i=0;i<persons.size();i++){
        	personNum.add(i);
        }
		List<Integer> attrNum=new LinkedList<Integer>();
        for(int i=0;i<attributes.size();i++){
        	attrNum.add(i);
        }
        //构造决策树
        buildDT(rootNode, "null", personNum, attrNum);
        //从决策树根节点的左边第一个孩子节点开始遍历作为最开始的currentNode
        currentNode = rootNode.getChilds().get(0);
		
        //System.out.println(rootNode);
    } // end of BinaryGuessPlayer()


    /**
     * 通过构造方法中初始化好的决策树来选取guess值
     * 规则:每次猜测currentNode
     */
    public Guess guess() {
    	// 判断当前节点是否存在personName,若存在输出猜测的候选人
		if (!currentNode.getPersonName().equals("")) {
			String personName = currentNode.getPersonName();
			return new Guess(GuessType.Person, "", personName);
		}
		// 若当前节点不存在personName,则说明未遍历到叶子节点,输出属性名及属性值
		else {
			String attrName = currentNode.getAttrName();
			String attrVal = currentNode.getAttrVal();
			return new Guess(GuessType.Attribute, attrName, attrVal);
		}
    } // end of guess()

    
    
    // 同Random的answer方法
	public boolean answer(Guess currGuess) {
		boolean result = false;
		// 若类型为person,则匹配人名
		if (currGuess.getType().equals(GuessType.Person) && chosenName.equals(currGuess.getValue())) {
			result = true;
		} // 若类型为attribute,则匹配属性名及特征值
		else if (currGuess.getType().equals(GuessType.Attribute)) {
			String chosenVal = chosenPerson.getAttributes().get(currGuess.getAttribute());
			if (chosenVal.equals(currGuess.getValue())) {
				result = true;
			}
		}
		return result;
    } // end of answer()

	/**
	 * 对猜测结果做处理,移动currentNode指向的节点.
	 * 如果currGuess.type为person
	 * 		answer只可能为真,返回true,游戏结束
	 * 如果currGuess.type为attribute
	 * 		answer为真,则将currentNode指向当前节点的左边第一个孩子节点
	 * 		answer为false.则将currentNode指向当前节点的右边第一个兄弟节点
	 */
	public boolean receiveAnswer(Guess currGuess, boolean answer) {
		boolean result = false;
		if (currGuess.getType().equals(GuessType.Person) && answer) {
			result = true;
		}else {
			if (answer) {
				currentNode = currentNode.getChilds().get(0);
			}else {
				//获取当前节点的父节点
				TreeNode parentNode = currentNode.getParentNode();
				//或许当前节点是其父节点的第几个孩子
				int num = parentNode.getChilds().indexOf(currentNode);
				//将currentNode指向其右边的兄弟节点,即父节点的下一个孩子节点
				currentNode = parentNode.getChilds().get(++num);
			}
		}
        return result;
    } 

	
	//给一个样本（数组中是各种情况的计数），计算它的熵
    public double getEntropy(int[] arr) {
        double entropy = 0.0;
        int sum = 0;
        for (int i = 0; i < arr.length; i++) {
            entropy -= arr[i] * Math.log(arr[i]+Double.MIN_VALUE)/Math.log(2);
            sum += arr[i];
        }
        entropy += sum * Math.log(sum+Double.MIN_VALUE)/Math.log(2);
        entropy /= sum;
        return entropy;
    }
    
    // 给定原始数据的子集(subset中存储行号),当以第index个属性为节点时计算它的信息熵
    public double calNodeEntropy(List<Integer> personNum, int index) {
        int sum = personNum.size();
        double entropy = 0.0;
        int[] count = new int[attributes.get(index).getAttrVal().size()];
        for (int i = 0; i < sum; i++) {
            int n = personNum.get(i);
            String attrName = persons.get(n).getAttributes().get(attributes.get(index).getAttrName());
            int nodeind = attributes.get(index).getAttrVal().indexOf(attrName);
            count[nodeind]++;
        }
        for (int i = 0; i < count.length; i++) {
            entropy += getEntropy(count) * count[i] / sum;
        }
        return entropy;
    }
    
   
    /**
     * 构造决策树
     * @param preNode 父节点
     * @param value
     * @param personNum 剩余待加入决策树的候选人的编号
     * @param attrNum 剩余待加入决策树的属性的编号
     */
    public void buildDT(TreeNode preNode, String value, List<Integer> personNum,
    		List<Integer> attrNum) {
    	if (personNum.size()==1) {
    		TreeNode treeNode = new TreeNode(persons.get(personNum.get(0)).getName(), "", "");
        	preNode.addChildNode(treeNode);
		}else{
			int maxIndex = -1;
	        double maxEntropy = -1;
	        for (int i = 0; i < attrNum.size(); i++) {
	            double entropy = calNodeEntropy(personNum, attrNum.get(i));
	            if (entropy > maxEntropy) {
	            	maxIndex = attrNum.get(i);
	                maxEntropy = entropy;
	            }
	        }
	        attrNum.remove(new Integer(maxIndex));
	        ArrayList<String> attvalues = (ArrayList<String>) attributes.get(maxIndex).getAttrVal();
	        for (String val : attvalues) {
	        	
	        	List<Integer> perNum = new ArrayList<Integer>();
	        	//构建子节点
	        	TreeNode treeNode = new TreeNode("", attributes.get(maxIndex).getAttrName(), val);
	            for (int i = 0; i < personNum.size(); i++) {
	                if (persons.get(personNum.get(i)).getAttributes().get(attributes.get(maxIndex).getAttrName()).equals(val)) {
	                	perNum.add(personNum.get(i));
	                }
	            }
	            if (perNum.size()==0) {
					continue;
				}else {
		        	preNode.addChildNode(treeNode);
				}
	            buildDT(treeNode, val, perNum, attrNum);
	        }
	    }
	}
	
	
	class Person {
		//候选人名
		private String name;
		//候选人特性
		private HashMap<String, String> Attributes = new HashMap<>();
		
		public String getName() {
			return name;
		}
		public void setName(String name) {
			this.name = name;
		}
		public HashMap<String, String> getAttributes() {
			return Attributes;
		}
		public void setAttributes(HashMap<String, String> attributes) {
			Attributes = attributes;
		}
	}

	class Attribute{
		private String attrName;
		private List<String> attrVal = new ArrayList<>();
		public String getAttrName() {
			return attrName;
		}
		public void setAttrName(String attrName) {
			this.attrName = attrName;
		}
		public List<String> getAttrVal() {
			return attrVal;
		}
		public void setAttrVal(List<String> attrVal) {
			this.attrVal = attrVal;
		}
		
	}
} // end of class BinaryGuessPlayer


/**
 * 决策树数据结构
 * @author Admin
 * * root节点为根节点,叶子节点为各个候选人,其余节点为条件
 */
class TreeNode{
	private TreeNode parentNode;//父节点
	private String personName="";//若为叶子节点时保存候选人名,其余情况均为空
	private String attrName="";//当前节点属性名
	private String attrVal="";//当前节点属性值
	private List<TreeNode> childs;//当前节点的子节点
	
	public TreeNode(String personName,String attrName,String attrVal){
		this.attrName = attrName;
		this.personName = personName;
		this.attrVal = attrVal;
	}
	public void setParentNode(TreeNode parentNode) {  
        this.parentNode = parentNode;  
    }
	
	public void addChildNode(TreeNode node){
		node.setParentNode(this); 
		if (childs==null) {
			this.childs = new ArrayList<>();
		}
		this.childs.add(node);
	}
	public String  toString(){
		return "personName:"+personName+"\n"+"attrName:"+attrName+"\n"+"attrVal:"+attrVal+"\n";
	}
	public String getPersonName() {
		return personName;
	}
	public void setPersonName(String personName) {
		this.personName = personName;
	}
	public String getAttrName() {
		return attrName;
	}
	public void setAttrName(String attrName) {
		this.attrName = attrName;
	}
	public String getAttrVal() {
		return attrVal;
	}
	public void setAttrVal(String attrVal) {
		this.attrVal = attrVal;
	}
	public List<TreeNode> getChilds() {
		return childs;
	}
	public void setChilds(List<TreeNode> childs) {
		this.childs = childs;
	}
	public TreeNode getParentNode() {
		return parentNode;
	}
}


